#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <unistd.h>
#include <pthread.h>

#define NTHREADS 4
#define DEGREE 62
#define ORDER (DEGREE)

typedef double keyType;
typedef struct BPNode{
	_Bool leaf;
	int numKeys;
	
	struct BPNode *parentNode;//for dependent root or not
	struct BPNode *prevNode;
	struct BPNode *nextNode;
	struct BPNode *childNode[2*ORDER];

	keyType keys[ORDER];
	char dataStr[ORDER][512];//这里就直接分配内存了，memcpy
}BPNode,*pBPNode;

typedef struct threadInputSet{
	pthread_mutex_t inputSetLock;
	pBPNode *root;
	keyType key;
	char string[512];
}threadInputSet;

pthread_mutex_t cntLock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t paraLock= PTHREAD_MUTEX_INITIALIZER;
volatile int threadCount = 0;

void buildTree(pBPNode *root);
//void insert(pBPNode *tree,keyType key,char *string);
void *insert(threadInputSet *parameter);
void *insertllt(threadInputSet *parameter);
void BPTreeInsertNotFull(BPNode *node,keyType key,char *string);
void BPTreeSplitChild(BPNode *parent,BPNode *node,int index);
void printTree(BPNode *tree);
void bufInsert();
void bufRemove();
void threadInsert(pBPNode *tree,keyType key,char *string);

int main(int argc,char **argv)
{
	BPNode *bRoot = NULL;
#if 0
	pthread_mutex_init(&paraLock,NULL);
	if(pthread_mutex_init(&cntLock,NULL) != 0){
		perror("init cntLock");
		exit(1);
	}
#endif
	buildTree(&bRoot);

//	printTree(bRoot);
	exit(0);
}

void bufInsert()
{
	pthread_mutex_lock(&cntLock);
	if(threadCount < NTHREADS)
		++threadCount;
	pthread_mutex_unlock(&cntLock);
}
void bufRemove()
{
	pthread_mutex_lock(&cntLock);
	if(threadCount > 0)
		--threadCount;
	pthread_mutex_unlock(&cntLock);
}

void buildTree(pBPNode *root)
{
	FILE *pfile = fopen("./assgn_bplus_data.txt","r");
	//FILE *pfile = fopen("./assgn_2.txt","r");
	if(pfile == NULL){
		perror("./assgn_bplus_data.txt");
		exit(1);
	}

	keyType key;
	char string[128];
	char dataString[512];

	while(fscanf(pfile,"%s	%s",string,dataString) != EOF){
		key = atof(string);
		while(threadCount > NTHREADS){
			//check
		}//直到线程池

		threadInsert(root,key,dataString);
	}
	fclose(pfile);
}

void threadInsert(pBPNode *tree,keyType key,char *string)
{
	pthread_t tid;

	//pthread_mutex_lock(&paraLock);
	//设置一个结构体，把参数传递进线程
	threadInputSet *pParameter = (threadInputSet *)calloc(sizeof(threadInputSet),1);
	pParameter->root = tree;
	pthread_mutex_init(&pParameter->inputSetLock,NULL);
	//pParameter->inputSetLock = PTHREAD_MUTEX_INITIALIZER;//PTHREAD_MUTEX_INITIALIZER
	pParameter->key = key;
	strncpy(pParameter->string,string,512);

	pthread_create(&tid,NULL,insert,pParameter);//???
	//pthread_join(tid,NULL);
}

void *insert(threadInputSet *parameter)
{
	sleep(1000);
	bufInsert();
	//pthread_detach(pthread_self());
	threadInputSet set = *parameter;
	//free(parameter);
	printf("%f	%s\n",set.key,set.string);
	free(parameter);
/*	pthread_mutex_lock(&parameter->inputSetLock);
	//pthread_mutex_lock(&paraLock);
	printf("%p\n",parameter);
	printf("%f, %s\n",parameter->key, parameter->string);
	//pthread_mutex_unlock(&paraLock);
	pthread_mutex_unlock(&parameter->inputSetLock);
	free(parameter);*/
	bufRemove();
/*
 *内存重用，或者线程资源回收
 * */	
	pthread_exit(NULL);
	//return NULL;
}




void printTree(BPNode *tree)
{
	BPNode *node = tree;
	while(node->childNode[0] != NULL){
		node = node->childNode[0];
	}
	while(node != NULL){
		int nums = node->numKeys;
		for(int i = 0;i < nums; i++){
			printf("%f,%s\n",node->keys[i],node->dataStr[i]);
		}
		node = node->nextNode;
	}
}

void *inserllt(threadInputSet *parameter)
{
	pBPNode *tree = parameter->root;
	keyType key = parameter->key;
	char *string = parameter->string;
	pthread_detach(pthread_self());

	BPNode *root = *tree;
	if(root == NULL){
		root = (pBPNode)calloc(sizeof(BPNode),1);
		if(!root){
			perror("insert--root");
			exit(1);
		}
		root->leaf = true;
		root->numKeys = 1;
		root->keys[0] = key;
		strcpy(root->dataStr[0],string);
#ifdef DEBUG_INSERT
		printf("node %f,%s\n",root->keys[0],root->dataStr[0]);
		//pause();
#endif
		*tree = root;
		return NULL;
	}
	if(root->numKeys >= (ORDER)){
		//分配新的节点，然后分离节点
		BPNode *newParent = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newParent){
			perror("insert-newParent");
			exit(1);
		}
		newParent->leaf = false;
		newParent->numKeys = 0;
		newParent->childNode[0] = root;
		*tree = newParent;//

		BPTreeSplitChild(newParent,root,0);//newParent 是新的根节点，root是当前节点了

		BPTreeInsertNotFull(newParent,key,string);//往已经更新的根节点插入
	}
	else {
		BPTreeInsertNotFull(root,key,string);
	}
	return NULL;
}

//把node的中间key给parent，以及分裂node
void BPTreeSplitChild(BPNode *parent,BPNode *node,int index)
{
	if(node->leaf){
		//在处理分裂出去的节点，新节点作为右节点
		BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newNode){
			perror("BPTreeSplitLeaf-newNode");
			exit(1);
		}
		newNode->leaf = true;
		//assign the parent
		newNode->parentNode = parent;
		newNode->numKeys = ORDER - ORDER/2;//lowBound
	//把node的右半部分的key转移到newNode中
		for(int i = ORDER/2; i < ORDER; i++){
			newNode->keys[i-ORDER/2] = node->keys[i];
			strcpy(newNode->dataStr[i-ORDER/2],node->dataStr[i]);
		
			node->keys[i] = 0;
			strcpy(node->dataStr[i],"#");
		}
	//resize the temporay node
		node->numKeys = (ORDER/2);
	//父节点的孩子节点
		parent->childNode[index] = node;
	//孩子的父节点assign the parent
		node->parentNode = parent;

	//处理parent,先调整父节点后半段的位置
		for(int i = parent->numKeys; i > index; --i){
			parent->childNode[i+1] = parent->childNode[i];
		}
		parent->childNode[index+1] =  newNode;
	//parent->keys[index] = node->keys[ORDER/2];
		for(int i = (parent->numKeys - 1);i >= index; --i){
			parent->keys[i+1] = parent->keys[i];
		}
		parent->keys[index] = newNode->keys[0];//alway is first key of newNode!!!!
		++parent->numKeys;
	//把leaf node连接起来!!!顺序很重要
		newNode->prevNode = node;
		if(node->nextNode != NULL){//nextNode != NULL
			node->nextNode->prevNode = newNode;
		}
		
		newNode->nextNode = node->nextNode;
		node->nextNode = newNode;
	}

	else{
		BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newNode){
			perror("BPTreeSplitChild-newNode");
			exit(1);
		}
		newNode->leaf = false;
		//newNode->parentNode = parent;
		//node->parentNode = parent;
		//fix the keys of new node
		//ORDER/2-1个key
		keyType startPointValue = node->keys[ORDER/2];
		for(int i = ORDER/2; i < ORDER; i++){
			newNode->keys[i-ORDER/2] = node->keys[i+1];//需要避开中间值
		
			node->keys[i] = 0;
		}
		//resize the keys of node and new node
		node->numKeys = ORDER/2;
		newNode->numKeys = ORDER/2-1;
		//patition children for the new node
		for(int i = ORDER/2;i < ORDER; i++){
			newNode->childNode[i-ORDER/2] = node->childNode[i+1];
			newNode->childNode[i-ORDER/2]->parentNode = newNode;
			node->childNode[i+1] = NULL;
		}
		//fix children for the current node 
		//if the current node is not the root node
		if(node->parentNode != NULL){
			//assign parents
			newNode->parentNode = parent;
			//insert to parent node(root)
			//处理parent,先调整父节点后半段的位置
			for(int i = parent->numKeys; i > index; --i){
				parent->childNode[i+1] = parent->childNode[i];
			}
			parent->childNode[index+1] =  newNode;
			//parent->keys[index] = node->keys[ORDER/2];
			for(int i = (parent->numKeys - 1);i >= index; --i){
				parent->keys[i+1] = parent->keys[i];
			}
			parent->keys[index] = startPointValue;//
			++parent->numKeys;
			//new we push up the splitting one level
		}
		else {
			//create a new parent node
			parent->leaf = false;
			//assign parents,
			node->parentNode = parent;
			newNode->parentNode = parent;
			//insert child
			parent->childNode[0] = node;
			parent->childNode[1] = newNode;
			//insert the key into the keys
			parent->keys[0] = startPointValue;
			++parent->numKeys;
		}
	}
}

void BPTreeInsertNotFull(BPNode *node,keyType key,char *string)
{
	//case1 node is leaf
	if(node->leaf){
		int i = node->numKeys - 1;
		while((i >= 0) && (key < (node->keys[i]))){
			node->keys[i+1] = node->keys[i];
			strcpy(node->dataStr[i+1],node->dataStr[i]);//node->dataStr[i+1]=node->dataStr[i];

			--i;
		}
		node->keys[i+1] = key;
		strcpy(node->dataStr[i+1],string);
		++node->numKeys;
	}
	//case2 node is interl
	else{
		int i = node->numKeys - 1;
		while((i >= 0) && (key < node->keys[i])){
			--i;
		}
		++i;
		if(node->childNode[i]->numKeys >= ORDER){
			BPTreeSplitChild(node,node->childNode[i],i);
			if(key > node->keys[i]){
				++i;
			}
		}
		BPTreeInsertNotFull(node->childNode[i],key,string);
	}
}

#ifdef DEBUG_ATFER_SPLIT
	printf("after split, insert\n");

//	printf("newParent: %x\n",newParent);
	for(int i=0;i<newParent->numKeys;i++){
		printf("%f,%s |%d| ",newParent->keys[i],newParent->dataStr[i],i);
	}
	printf("\n");

//	printf("newParent:childNode 0 %x\n",&newParent->childNode[0]);
	for(int i=0;i<newParent->childNode[0]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[0]->keys[i],newParent->childNode[0]->dataStr[i],i);
	}
	printf("\n");
//	printf("newParent:childNode 1 %x\n",&newParent->childNode[1]);
	for(int i=0;i<newParent->childNode[1]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[1]->keys[i],newParent->childNode[1]->dataStr[i],i);
	}
	printf("\n");
//	pause();
#endif
#ifdef DEBUG_ATFER_SPLIT
	printf("after insert\n");

//	printf("newParent: %x\n",newParent);
	for(int i=0;i<newParent->numKeys;i++){
		printf("%f,%s |%d| ",newParent->keys[i],newParent->dataStr[i],i);
	}
	printf("\n");

//	printf("newParent:childNode 0 %x\n",&newParent->childNode[0]);
	for(int i=0;i<newParent->childNode[0]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[0]->keys[i],newParent->childNode[0]->dataStr[i],i);
	}
	printf("\n");
//	printf("newParent:childNode 1 %x\n",&newParent->childNode[1]);
	for(int i=0;i<newParent->childNode[1]->numKeys;i++){
		printf("%f,%s |%d| ",newParent->childNode[1]->keys[i],newParent->childNode[1]->dataStr[i],i);
	}
	printf("\n");
	pause();
#endif

